#include <iostream>
#include <stdio.h>
#include <cstdlib>
#include <fstream>


class HashNode    //HashNode
{
    public:
        char* word;
        int count=0;
        HashNode* next;
        HashNode(){word = NULL; count = 0; next = NULL;};
};

HashNode* slot[29989];    //slots

void HashBegin()    //chu shi hua all slots
{
    for(int i = 0; i < 29989; i++)
    {
        slot[i] = new HashNode;
        slot[i]->next = NULL;
        slot[i]->word = NULL;
        slot[i]->count = 0;
    }
}

unsigned int get_key(const char* _word)    //get key
{
    unsigned int index = 0;
    for(; *_word != '\0'; _word++)
    index = index * 31 + (*_word - 'a');
    return index % 29989;
}

void insertword(char* _word)    //insert word from txt
{
    HashNode* p;
    if(_word == NULL)
    return;
    unsigned int index = get_key(_word);
    p = slot[index];
    if(p->word == NULL)
    {
		p->word = _word;
		p->count += 1;
		p->next = NULL;
		slot[index] = p;
		return;
	}
    else
    {
	    slot[index]->count += 1;
	    for(p = slot[index]; p->next != NULL; p = p->next);
	    HashNode* q = new HashNode;
	    q->count = 0;
	    q->word = _word;
	    q->next = NULL;
	    p->next = q;
	    return;
    }
}


char* change(char* s)    //change A <= s[i] <= Z to a <= s[i] <= z
{
    int i = 0, j = 0;
    char* m = new char[15];
    char a;
    while(s[i] != '\0')
    {
	    if(s[i] >= 'A' && s[i] <= 'Z')
	    s[i] = s[i] + ('a' - 'A');
        a = s[i];

        if(a >= 'a' && a <= 'z')
        {
        	m[j] = a;
        	j++;
        }
        i++;
    }
    m[j] = s[i];
    return m;
}

void get_words_from_txt()  //read and get words from txt
{
    char* s = new char[15];
    while(std::cin >> s)
    {
        s = change(s);
        insertword(s);
        s = new char[15];
    }
}

void Hash()    //hash table ,main
{
    HashNode* a[29989];
    HashNode* tmp;
    int s = 0;
    for(int i = 0; i < 29989; i++)
    {
        a[i] = new HashNode;
        a[i]->next = NULL;
        a[i]->word = NULL;
        a[i]->count = 0;
    }
    for(int i = 0, j = 0; i < 29989; i++)
    {
        if(slot[i]->count != 0)
        {
            a[j] = slot[i];
            s++;
            j++;
        }
    }
    for(int i = 0; i < s; i++)
    {
        for(int j = s - 1; j > i; j--)
        if(a[j]->count > a[j-1]->count)
        {
			tmp = a[j];
			a[j] = a[j-1];
			a[j-1] = tmp;
		}
    }
    for(int i = 0; i < 20; i++)
    {
        std::cout << a[i]->word << "            " << a[i]->count << std::endl;
    }
}

